/**
 * @program: leetcode021
 * @author: JCM
 * @create: 2023-03-02 21:28
 * @description:
 **/
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Main {

    /**
     * 递归法
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        // 当 l1.val < l2.val 时，再比较 l1.next 和 l2
        if(l1.val < l2.val) {
            l1.next = mergeTwoLists1(l1.next,l2);
            return l1;
        }else {
            l2.next = mergeTwoLists1(l2.next,l1);
            return l2;
        }

    }

    /**
     * 普通方法
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        // 注意：head 和 tail 一定要设置为 null，否则会失败
        // head 定位返回的链表的头结点，tail 起到连接链表的作用
        ListNode head = null;
        ListNode tail = null;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                // l1.val < l2.val 则返回链表的头结点，就是 l1
                if(head == null) {
                    head = tail = l1;
                }else {
                    tail.next = l1;
                    tail = l1;
                }
                l1 = l1.next;
            }else {
                if(head == null) {
                    head = tail = l2;
                }else {
                    tail.next = l2;
                    tail = l2;
                }
                l2 = l2.next;
            }
        }
        // l1 不为空时，将 tail 和 l1 连接起来
        if(l1 != null) {
            tail.next = l1;
        }else {
            tail.next = l2;
        }
        return head;
    }
}
